﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0085_Rob2 : IAlgorithm
    {
        // 213. 打家劫舍 II

        // 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
        // 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
        // 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

        // 提示：
        //  1 <= nums.length <= 100
        //  0 <= nums[i] <= 1000

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 2, 3 };
            // 算法执行与打印
            Console.WriteLine(Rob(nums));
        }

        // 算法
        // 偷和不偷
        public int Rob(int[] nums)
        {
            if (nums.Length == 1)
                return nums[0];
            return Math.Max(Rob(nums, 0, nums.Length - 1), Rob(nums, 1, nums.Length));
        }
        private int Rob(int[] nums, int start, int length)
        {
            var dp = new int[2];
            dp[0] = nums[start];
            dp[1] = 0;
            for (int i = start + 1; i < length; i++)
            {
                var temp = nums[i] + dp[1];
                dp[1] = Math.Max(dp[1], dp[0]);
                dp[0] = temp;
            }
            return Math.Max(dp[0], dp[1]);
        }
    }
}
